重複ポリトープを介した幾何学的要素による点の順序集合の近似

专利摘要:
それぞれが基準点と付随する許容偏差とを含む物理的な点の順序集合が、パラメトリック空間内でポリトープを交差させる方法によって決定された幾何学的要素のシーケンスによって近似される。物理的な点の第１のサブグループを接続する幾何学的要素の第１の束が生成され、第１のポリトープに写像される。物理的な点の第２のサブグループを接続する幾何学的要素の第２の束が生成され、第２のポリトープに写像される。第１のポリトープと第２のポリトープとの間の交差がヌルでない場合は、交差領域内の点は、結合された２つのサブグループ内の物理的な点を近似する幾何学的要素に対応する。この工程は、さらなるサブグループに対して反復して繰り返される。最終交差領域の中心点は、幾何学的要素の最良適合近似に対応する。
公开号:JP2011510421A
申请号:JP2010544311
申请日:2009-01-20
公开日:2011-03-31
发明作者:ロギノフ，イゴール，ヴァディモビッチ
申请人:トップコン ジーピーエス，エルエルシー；
IPC主号:G06T11-20

专利说明:

[0001] 本発明は、一般に幾何学的要素の配列による点の順序集合の近似に関し、より詳細には、各点の位置が非ゼロ精度で決定される点の順序集合の近似に関する。]
背景技術

[0002] 様々な応用分野で、幾何学的特徴は、点の順序集合として表現され得る。国土調査において、道路、河川、および領土の境界は、点の順序集合で表され得る。コンピュータビジョンシステムにおいて、対象物の境界は、点の順序集合で表され得る。デジタルイメージプロセッシングにおいて、イメージ内の対象物の輪郭は、点の順序集合（ピクセル）で表現され得る。未処理の点の集合を解析するには、強力なプロセッサ、大規模なメモリ、および複雑なアルゴリズムを有するコンピュータシステムが必要である。幾何学的要素の配列を有する点の集合を近似することによって、より効率的な解析が遂行され得る。例えば道路は、セグメントの連鎖（シーケンス）としてモデル化され得る。基本セグメントは、直線セグメントと円弧とを含む。必要であれば、隣接するセグメント間を滑らかに推移するために、さらに複雑な幾何学的曲線が使用され得る。より効率的な解析に加えて、幾何学的要素の配列による近似によって、データ圧縮のための機構が与えられる。未処理の点の集合は、一層小さい幾何学的パラメータの集合によって特徴付けられ得る。例えば、直線セグメント上に含まれる点の配列は、そのセグメントの２つの終点の座標で特徴付けられ得る。同様に、円弧上に含まれる点の配列は、円弧の２つの終点の座標と円弧上にある第３の点の座標で特徴付けられ得る。]
発明が解決しようとする課題

[0003] 点は幾何学的抽象化であることに注意されたい。現実の応用においては、具体的な位置は非ゼロ精度内で決定され得る。国土調査において、例えば、精度は測定システム（およびその他の因子）の分解能と誤差の関数である。デジタルイメージシステムにおいて、精度はデジタルイメージのピクセル寸法（およびその他の因子）の関数である。データ圧縮において、精度は（ユーザ定義された）許容できる情報の損失の値の関数であり、圧縮率（およびその他の因子）で記述することができる。必要とされるものは、各点の位置が非ゼロ精度を有し、幾何学的要素の配列を持つ点の順序集合を近似する方法である。]
課題を解決するための手段

[0004] 本発明の一実施形態において、物理的空間内の物理的な点の順序集合の近似は、パラメトリック空間内でポリトープを交差させる方法で実行される。各物理的な点は、基準点と付随する許容偏差とを含む。物理的な点の順序集合から選択された物理的な点の第１のサブグループを接続する幾何学的要素の第１の束が生成される。第１の束内の各幾何学的要素の、第１のサブグループ内の各基準点からの偏差は、第１のサブグループ内の各基準点に付随する許容偏差を超えない。次に第１の束は、パラメトリック空間内の第１のポリトープに写像され、第１の束内の各幾何学的要素は、第１のポリトープ内の対応するパラメトリックな点に写像される。物理的な点の順序集合から選択された物理的な点の第２のサブグループを接続する幾何学的要素の第２の束が生成される。第２の束内の各幾何学的要素の、第２のサブグループ内の各基準点からの偏差は、第２のサブグループ内の各基準点に付随する許容偏差を超えない。次に第２の束は、パラメトリック空間内の第２のポリトープに写像され、第２の束内の各幾何学的要素は、第２のポリトープ内の対応するパラメトリックな点に写像される。第１のポリトープと第２のポリトープとの間の交差がヌルでない場合は、交差領域内の点は、結合された２つのサブグループ内の物理的な点を近似する幾何学的要素に対応する。交差領域の中心は、最初の２つのサブグループ内の物理的な点を近似する幾何学的要素の最良適合近似に対応する。
本発明の、これらのおよびその他の利点は、下記の詳細な説明および添付する図面を参照することによって、当業者に明らかになるであろう。]
図面の簡単な説明

[0005] 直線セグメントの束で接続された２つの物理的な点の物理的空間内におけるプロットを示す図である。
２つの直線セグメントの束で接続された３つの物理的な点の物理的空間内におけるプロットを示す図である。
物理的空間内における４つの点のうち、第１の円弧の束で接続された最初の３つの点のプロットを示す図である。
物理的空間内における４つの点のうち、第２の円弧の束で接続された残りの３つの点のプロットを示す図である。
パラメトリックな点に写像された、２つのポリゴンを形成する直線セグメントの２つの束の、パラメトリック空間内におけるプロットを示す図である。
円弧に対応する円の中心点に写像された、物理的空間内の円弧のプロットを示す図である。
円弧に対応する円の中心点に写像された、２つの円弧の束の物理的空間内におけるプロットを示す図である。
直線セグメントと円弧との接続された配列によって近似された、物理的な点の複雑な順序集合の例を示す図である。
本発明の一実施形態に従った、物理的な点の順序集合を近似する最良適合近似の直線セグメントを決定するためのステップの流れ図である。
コンピュータの高いレベルの概略図である。
可動型ＧＰＳ受信機による物理的な点の順序集合の測定を示す図である。
誘導制御システムに誘導される車両の概略を示す図である。]
実施例

[0006] 現実空間（物理的空間とも呼ばれる）における位置は基準座標系に対する点の座標で規定することができる。例えば、標準的な直角Ｘ−Ｙ−Ｚ基準座標系に対して、点Ｐは座標（ｘＰ，ｙＰ，ｚＰ）で表され得る。数学的な点は無次元である。しかし実際には物理的な点は空間的に分布しており、すなわち物理的な点の位置は非ゼロ範囲内で決定され、それは、測定システムの分解能および安定度、ならびに環境条件（これには、温度、湿度、衝撃、および振動を含む）などの複数の因子に依存することがある。いくつかの測定システムに対して、熱的ノイズ、電磁的ノイズ、および電磁的干渉が働くこともある。物理的な点Ｐは座標（ｘＰ±ΔｘＰ，ｙＰ±ΔｙＰ，ｚＰ±ΔｚＰ）で表すことができ、ここで（ΔｘＰ，ΔｙＰ，ΔｚＰ）は精度を表し、（ｘＰ，ｙＰ，ｚＰ）は精度と一緒に決定され得る。一般に（ΔｘＰ，ΔｙＰ，ΔｚＰ）は一定値でなく、（ｘＰ，ｙＰ，ｚＰ）とともに変化し得る。したがって２次元では、物理的な点Ｐは、矩形の範囲（ｘＰ±ΔｘＰ，ｙＰ±ΔｙＰ）で表すことができる。同様に３次元では、物理的な点Ｐは、直角プリズム（ｘＰ±ΔｘＰ，ｙＰ±ΔｙＰ，ｚＰ±ΔｚＰ）で表すことができる。]
[0007] 本発明の一実施形態において、座標を適切なリニアスケールとすることよって、スケール付き座標系内のほぼすべての点に対してΔｘＰ＝ΔｙＰ＝ΔｚＰとすることができるので、精度は等方性と考えられる。スケーリングされない場合は、各物理的な点Ｐに対して、値ΔｘＰ、ΔｙＰ、およびΔｚＰはすべて（ΔｘＰ，ΔｙＰ，ΔｚＰ）の最小値に設定され得る。したがって、物理的な点Ｐは２次元では円形の範囲で、３次元では球形で表され得る。２次元では物理的なＰは、［ＰＰ（ｘＰ，ｙＰ），ＲＰ］で表すことができ、ここでＰＰ（ｘＰ，ｙＰ）は円の中心点であり、ＲＰは円の半径である。同様に３次元では、物理的なＰは、［ＰＰ（ｘＰ，ｙＰ，ｚＰ），ＲＰ］で表すことができ、ここでＰＰ（ｘＰ，ｙＰ，ｚＰ）は球の中心点であり、ＲＰは球の半径である。ここでＰＰは物理的な点Ｐの対応基準点とも呼ばれ、ＲＰは物理的な点Ｐに付随する許容偏差とも呼ばれ基準点ＰＰに付随するものである。基準点および許容偏差は、様々な手段で決定することができる。例えば、基準点は単一計器の読み値であってよく、許容偏差は較正手順で規定された精度であってよい。基準点および許容偏差は、複数の測定を行って統計的に決定することもできる。例えば、基準点は平均値または中央値によって規定することができ、許容偏差は標準偏差によって、または極値によって規定することができる。]
[0008] 本発明の一実施形態において物理的な点の順序集合は、それぞれ対応基準点および付随する許容偏差を有し、直線セグメントおよび円弧のような簡単な幾何学的要素の連鎖（シーケンス）によって近似することができる。適用対象によって一層複雑な曲線を使ってもよい。連鎖の中で各要素は連続した物理的な点の最大の数を近似し、それによって各要素の各物理的な点からの偏差が物理的な点に付随する許容偏差内になるようにする。本明細書では、要素の物理的な点からの偏差は、要素の物理的な点に対応する基準点からの偏差を指す。本明細書では、単一の要素で近似された物理的な点のグループは、その要素に付随する物理的な点のサブグループを指す。]
[0009] 同じサブグループの物理的な点は、複数の要素で近似され得る。本明細書では、同じサブグループを近似し得る要素の集合は要素の束を指す。本明細書では、束内の要素は関連する束のメンバ要素を指す。各メンバ要素は同じ形状を有するが、幾何学的パラメータは異なる。例えば、束が直線セグメントの集合を含む場合、各メンバ要素は異なる値の傾きおよび切片を有し得る。束が円弧を含む場合は、各メンバ要素は異なる中心点および半径を有し得る。]
[0010] 本発明の一実施形態において、束内の各メンバ要素はパラメトリックな点に写像される。直線セグメントに対して、ユーザ規定のパラメトリック座標を有する、ユーザ規定のパラメトリック空間に、パラメトリックな点が定義される。したがって束は物理的空間内の要素のマニホルドであり、要素のマニホルドはパラメトリック空間内のパラメトリックな点のマニホルドに写像され得る。検討および図面を簡潔にするために、例には２次元空間が使用される。３次元空間に対する実施形態は、２次元空間に対する詳細な例が示された後でまとめられる。２次元において、パラメトリックな点のマニホルドは、２次元パラメトリック空間内に領域を形成する。本発明の一実施形態において、この領域はポリゴンで近似され、ポリゴン内のすべての点はパラメトリック空間からのパラメトリックな点のマニホルドのメンバである。]
[0011] 直線セグメントを含む要素の例を、図１、図２、図４、および図７を参照して最初に検討する。円弧を含む要素の例は、図３Ａ、図３Ｂ、図５Ａ、および図５Ｂを参照してその次に検討する。] 図１ 図２ 図３Ａ 図３Ｂ 図４ 図５Ａ 図５Ｂ 図７
[0012] 図１は、隣接する２つの物理的な点Ｐ１ １０６（基準点Ｐ１ １０２、および半径Ｒ１ １０４を有する）、およびＰ２ １４６（基準点Ｐ２ １４２、および半径Ｒ２ １４４を有する）を含む単純な幾何学的構成を例示するものである。点の座標は、物理的空間内のＸ軸１０１、およびＹ軸１０３に関して測定される。半径Ｒ１ １０４は、基準点Ｐ１ １０２からの許容偏差を表し、半径Ｒ２ １４４は、基準点Ｐ２ １４２からの許容偏差を表す。物理的な点Ｐ１ １０６と物理的な点Ｐ２ １４６は、直線セグメントの束Ｂ１９１で接続されている。束Ｂ１９１の外側境界は直線セグメントＬ１ １２１および直線セグメントＬ２ １２２である。直線セグメントＬ３ １２３および直線セグメントＬ４ １２４は、傾きの範囲の境界を画定する直線セグメントである。] 図１
[0013] 図２には、３つの物理的な点がＰ１ ２０６（基準点Ｐ１ ２０２および半径Ｒ１ ２０４を有する）、Ｐ２ ２４６（基準点Ｐ２ ２４２および半径Ｒ２ ２４４を有する）、およびＰ３ ２８６（基準点Ｐ３ ２８２および半径Ｒ３ ２８４を有する）の順にある。物理的な点Ｐ１ ２０６および物理的な点Ｐ２ ２４６は、直線セグメントの第１の束Ｂ１ ２９１で接続されている。束Ｂ１ ２９１の外側境界は、直線セグメントＬ１ ２２１、および直線セグメントＬ２ ２２２である。直線セグメントＬ３ ２２３、および直線セグメントＬ４ ２２４は、束Ｂ１ ２９１内の傾きの範囲の境界を画定する直線セグメントである。同様に、物理的な点Ｐ２ ２４６および物理的な点Ｐ３ ２８６は、直線セグメントの第２の束Ｂ２ ２９２で接続されている。束Ｂ２ ２９２の外側境界は、直線セグメントＬ５ ２２５、および直線セグメントＬ６ ２２６である。直線セグメントＬ７ ２２７、および直線セグメントＬ８ ２２８は、束Ｂ２ ２９２内の傾きの範囲の境界を画定する直線セグメントである。] 図２
[0014] 物理的空間（図２）内で、各束内の直線セグメントは一般的な線形方程式の集合によって定義された直線に含まれる。
Ａ＊ｘ＋Ｂ＊ｙ＋Ｃ＝０ （Ｅ１）
ここで、Ａ、Ｂ、Ｃは線形係数である。
図４はユーザ定義されたパラメトリック空間内の対応するプロットの例を示す。図４に示された実施形態において、水平軸（横軸）は（Ｃ／Ｂ）４０１であり、垂直軸（縦軸）は（Ａ／Ｂ）４０３である。パラメトリック空間内の点Ｐの座標は、［（Ｃ／Ｂ）ｐ，（Ａ／Ｂ）ｐ］である。図４の縦軸は細部を十分に示すために１０倍の比率になっていることに注意されたい。図４において、プロットされた各パラメトリックな点は、図２の直線セグメントに対応する。
Ｐ１ ４２１←→Ｌ１ ２２１
Ｐ２ ４２２←→Ｌ２ ２２２
Ｐ３ ４２３←→Ｌ３ ２２３
Ｐ４ ４２４←→Ｌ４ ２２４
Ｐ５ ４２５←→Ｌ５ ２２５
Ｐ６ ４２６←→Ｌ６ ２２６
Ｐ７ ４２７←→Ｌ７ ２２７
Ｐ８ ４２８←→Ｌ８ ２２８] 図２ 図４
[0015] 頂点Ｐ１ ４２１、Ｐ２ ４２２、Ｐ３ ４２３、およびＰ４ ４２４で定義されるポリゴンＳ１ ４４１は（図４）、物理的な点Ｐ１ ２０６と物理的な点Ｐ２ ２４６を接続する、直線セグメントの束Ｂ１ ２９１に対応する（図２）。すなわち、ポリゴンＳ１ ４４１内の各点は、束Ｂ１ ２９１内の直線セグメントに対応する。同様に、頂点Ｐ５ ４２５、Ｐ６ ４２６、Ｐ７ ４２７、およびＰ８ ４２８で定義されるポリゴンＳ２ ４４２は（図４）、物理的な点Ｐ２ ２４６と物理的な点Ｐ３ ２８６を接続する、直線セグメントの束Ｂ２ ２９２に対応する（図２）。すなわち、ポリゴンＳ２ ４４２内の各点は束Ｂ２ ２９２内の直線セグメントに対応する。図４において重複領域σ４４３は、ポリゴンＳ１ ４４１とポリゴンＳ２ ４４２との間の交差を表す。したがって重複領域σ４４３内の各パラメトリックな点は、物理的な点Ｐ１ ２０６、物理的な点Ｐ２ ２４６、および物理的な点Ｐ３ ２８６を接続する直線セグメントに対応する（図２）。各直線セグメントの各基準点Ｐ１ ２０２、基準点Ｐ２ ２４２、および基準点Ｐ３ ２８２からの偏差は、各基準点に付随する許容偏差以下である。] 図２ 図４
[0016] 本工程は、図７の流れ図に示すように、追加の隣接する物理的な点に対して繰り返すことが可能である。本工程への入力７０２は、物理的な点の集合順序集合Ｐｉ，ｉ＝１・・・Ｎ，Ｎ≧３である。物理的な点Ｐｉは対応する基準点Ｐｉ、および付随する許容偏差（半径）Ｒｉで表される。ステップ７０４で束Ｂ１が生成され、パラメトリック空間内のポリゴンＳ１に写像される。
Ｂ１→Ｓ１
束Ｂ１は、物理的な点Ｐ１と物理的な点Ｐ２を接続する直線セグメントの集合を含み、基準点Ｐ１からの各直線セグメントの偏差が許容偏差Ｒ１以下であり、基準点Ｐ２からの各直線セグメントの偏差が許容偏差Ｒ２以下であるようにする。] 図７
[0017] ステップ７０６で初期交差領域σ１はＳ１の値を指定される。添字ｊは値２に初期化される。添字ｊは１対の点（Ｐｊ，Ｐｊ＋１）を接続する直線セグメントの束の添字であるから、ｊの最大値は（Ｎ−１）である。ステップ７０８で束Ｂｊが生成され、パラメトリック空間のポリゴンＳｊに写像される。
Ｂｊ→Ｓｊ
ステップ７１０で交差σｊは、σｊ−１とＳｊの交差として定義される（σｊ−１∩Ｓｊと表示される）。
σｊ＝σｊ−１∩Ｓｊ]
[0018] 工程は次にステップ７１２に移り、そこで交差σｊはチェックされてそれがヌルであるか決められる。交差σｊがヌルの場合は、工程はステップ７１４に移り、そこで前の非ゼロ交差を示すために最終添字ｆは値（ｊ−１）として定義される。工程は次にステップ７１４からステップ７２２に移るが、それについては以下でさらに検討する。ステップ７１２で交差σｊがヌルでない場合は、工程は次にステップ７１６に移る。ステップ７１６で添字ｊがチェックされ、点の集合（入力７０２）の全Ｎ点が処理されたか判定される。全Ｎ点が処理された場合は、工程は次にステップ７１８に移り、そこで最終添字ｆは値ｊに決められる。工程は次にステップ７１８からステップ７２２に移る。全Ｎ点が処理されていない場合（ステップ７１６）は、工程は次にステップ７２０に移り、そこで添字ｊは１だけ増加され、そのときの非ヌル交差を示す。]
[0019] ステップのシーケンス（ステップ７０８、ステップ７１０、ステップ７１２、ステップ７１６、およびステップ７２０）は、新しい交差がヌルになる（ステップ７１２）か、または全Ｎ点が処理される（ステップ７１６）まで繰り返される。次に工程はステップ７２２に移り、そこで最終交差領域σｆの幾何学的基準中心点が決定される。一般に、最終交差領域は、側の長さが必ずしも等しくなく、隣接する側の間の角度が必ずしも等しくない１つのポリゴンである。幾何学的基準中心点はユーザ定義された基準に従って決定してよい。例えば、ポリゴンが対称性の中心を有するときは、幾何学的基準中心点は対称性の中心として定義してよい。別の例で、対称性の中心がない場合は、幾何学的基準中心点はポリゴンの重心として定義してよい。本明細書では、ポリゴンの幾何学的基準中心点は、ポリゴンの中心とも呼ばれる。σｆの幾何学的基準中心点をパラメトリックな点Ｐｆ［（Ｃ／Ｂ）ｆ，（Ａ／Ｂ）ｆ］として指定する。次にステップ７２４でＰｆ［（Ｃ／Ｂ）ｆ，（Ａ／Ｂ）ｆ］は写像により、物理的空間内の線になる。
Ａｆ＊ｘ＋Ｂｆ＊ｙ＋Ｃｆ＝０ （Ｅ２）
出力７２６は、最初の隣接するｆ＋１個の物理的な点の間の最良適合近似（後に記すさらなる検討を参照せよ）である、直線セグメントを含む直線の式であり、直線セグメントの対応する各基準点からの偏差が、各基準点に付随する許容偏差以下であるようにする。]
[0020] 最終直線セグメントによって近似できる物理的な点の全数（Ｔ）は、次式で決定される。
［σ２＝（σ１∩Ｓ２）≠φ；σ３＝（σ２∩Ｓ３）＝φ］→Ｔ＝３
［σ３＝（σ２∩Ｓ３）≠φ；σ４＝（σ３∩Ｓ４）＝φ］→Ｔ＝４
・・・・・・・・・・・・・・・・・
［ｆ≧２；σｆ＝（σｆ−１∩Ｓｆ）≠φ；σｆ＋１＝（σｆ∩Ｓｆ＋１）＝φ］→Ｔ＝ｆ＋１]
[0021] 一実施形態において最良適合の直線セグメントは、比率（偏差ｎｋ／Ｒｋ）の和が最小になるように決定される。ここで、Ｒｋは物理的な点Ｐｋに対する許容偏差、偏差ｎｋはｋ番目の点の直線セグメントからの偏差の絶対値であり、和はＴ個の物理的な点にわたるものである。一般に、最良適合の直線セグメントは、写像により最終的な非ヌル交差領域内のパラメトリックな点になる。一実施形態において、最終的な非ヌル交差領域は最終的な非ヌルポリゴンで近似され、最終的な非ヌルポリゴンの中心は、写像により最良適合の直線セグメントを詳細に近似する直線セグメントになる。この方法は、最良適合の直線に対応するパラメトリックな点を決定することよりも、最終的な非ヌルポリゴンの中心を決定することの方が、数学的に複雑でないので有利である。そのため、必要なコンピュータ資源をより少なくでき、計算速度を増加できる。]
[0022] 図４に示す本発明の一実施形態において、パラメトリック座標が（Ｃ／Ｂ，Ａ／Ｂ）であるユーザ定義されたパラメトリック空間内の点が、複数の点のサブグループを１つの直線セグメントで近似するために使用された。別の実施形態において、パラメトリック座標が（Ｃ／Ｂ，Ａ／Ｂ）であるユーザ定義されたパラメトリック空間内の点が、複数の点のサブグループを１つの直線セグメントで近似するために使用され得る。パラメトリック座標（Ｃ／Ｂ，Ａ／Ｂ）は、直線セグメントが水平軸に近い空間構成に対して有利である。同様にパラメトリック座標（Ｃ／Ａ，Ｂ／Ａ）は、直線セグメントが垂直軸に近い空間構成に対して有利である。一般に、パラメトリック空間内の座標はユーザ定義されたものであり、直角座標である必要はない。例えば、パラメトリック空間内の座標は円柱座標であってよい。] 図４
[0023] 図３Ａ、図３Ｂ、図５Ａ、および図５Ｂは円弧を構成する要素のための例を示す。図３Ａには、４つの物理的な点が、物理的な点Ｐ１ ３０６（基準点Ｐ１ ３０２、および半径Ｒ１ ３０４）、物理的な点Ｐ２ ３２６（基準点Ｐ２ ３２２、および半径Ｒ２ ３２４）、物理的な点Ｐ３ ３４６（基準点Ｐ３ ３４２、および半径Ｒ３ ３４４）、物理的な点Ｐ４ ３６６（基準点Ｐ４ ３６２、および半径Ｒ４ ３６４）、の順にある。この例において、最初の３つの物理的な点Ｐ１ ３０６、Ｐ２ ３２６、Ｐ３ ３４６は、円弧の束Ｂ１ ３９１で接続されている。円弧Ａ１ ３８１〜円弧Ａ６ ３８６は束 Ｂ１ ３９１の外側境界である。束Ｂ１ ３９１内の各円弧に対して、各基準点Ｐ１ ３０２、Ｐ２ ３２２、およびＰ３ ３４２からの偏差は、各基準点に付随する許容偏差（それぞれ、Ｒ１ ３０４、Ｒ２ ３２４、およびＲ３ ３４４）以下である。] 図３Ａ 図３Ｂ 図５Ａ 図５Ｂ
[0024] 図３Ｂに、４つの物理的な点Ｐ１ ３０６、Ｐ２ ３２６、Ｐ３ ３４６、およびＰ４ ３６６の同様なシーケンスが示される。この例では、残りの３つの物理的な点Ｐ２ ３２６、Ｐ３ ３４６、およびＰ４ ３６６が円弧の束Ｂ２ ３９２で接続されている。円弧Ａ７ ３８７〜円弧Ａ１２ ３８１２は束Ｂ２ ３９２の外側境界である。束Ｂ２ ３９２内の各円弧の、各基準点Ｐ２ ３２２、Ｐ３ ３４２、およびＰ４ ３６２からの偏差は、各基準点に付随する許容偏差（それぞれ、Ｒ２ ３２４、Ｒ３ ３４４、およびＲ４ ３６４）以下である。] 図３Ｂ
[0025] 本発明の一実施形態において、円弧はユーザ定義されたパラメトリック空間内の単一のパラメトリックな点に写像される。一実施形態において、パラメトリック空間もやはり物理的空間である。すなわち、水平軸（横軸）はＸ軸１０１であり、縦軸はＹ軸１０３である（図３Ａ、および図３Ｂ）。円柱座標のような非直角座標も使用できる。パラメトリックな点は円弧に対応する円の中心点である。本明細書では円弧に対応する円の中心点は円弧の中心と呼ばれる。図５Ａは写像の例を示す。図５Ａで点ＰＮは抽象的な数学的点を示し、Ｎは整数である。点Ｐ１ ５０１、Ｐ２ ５０２、およびＰ３ ５０３は、中心点Ｖ１ ５１１および半径Ｒ１ ５３１を有する円弧Ａ１ ５２１で近似される。点Ｐ２ ５０２、Ｐ３ ５０３、およびＰ４ ５０４は、中心点Ｖ２ ５１２および半径Ｒ２ ５３２を有する円弧Ａ２ ５２２で近似される。円弧Ａ１ ５２１はパラメトリックな点Ｖ１ ５１１に写像され、円弧Ａ２ ５２２はパラメトリックな点Ｖ２ ５１２に写像される。] 図３Ａ 図３Ｂ 図５Ａ
[0026] 図５Ｂは、図３Ａおよび図３Ｂに示す幾何学的なプロットに対応するパラメトリックなプロットを示す。図５Ｂにおいて、各パラメトリックな点は図３Ａおよび図３Ｂ内の（対応する半径を有する）円弧の中心に対応する。
Ｖ１ ５８１←→Ａ１ ３８１
Ｖ２ ５８２←→Ａ２ ３８２
Ｖ３ ５８３←→Ａ３ ３８３
Ｖ４ ５８４←→Ａ４ ３８４
Ｖ５ ５８５←→Ａ５ ３８５
Ｖ６ ５８６←→Ａ６ ３８６
Ｖ７ ５８７←→Ａ７ ３８７
Ｖ８ ５８８←→Ａ８ ３８８
Ｖ９ ５８９←→Ａ９ ３８９
Ｖ１０ ５８１０←→Ａ１０ ３８１０
Ｖ１１ ５８１１←→Ａ１１ ３８１１
Ｖ１２ ５８１２←→Ａ１２ ３８１２] 図３Ａ 図３Ｂ 図５Ｂ
[0027] 頂点Ｖ１ ５８１〜Ｖ６ ５８６で定義されるポリゴンＳ１ ５４４１（図５Ｂ）は、物理的な点Ｐ１ ３０６、物理的な点Ｐ２ ３２６、および物理的な点Ｐ３ ３４６を接続する、円弧の束Ｂ１ ３９１（図３Ａ）に対応する。すなわち、ポリゴンＳ１ ５４４１内の各点は、束Ｂ１ ３９１内の円弧の中心に対応する。同様に、頂点Ｖ７ ５８７〜Ｖ１２ ５８１２で定義されるポリゴンＳ２ ５４４２（図５Ｂ）は、物理的な点Ｐ２ ３２６、物理的な点Ｐ３ ３４６、および物理的な点Ｐ４ ３６６を接続する、円弧の束Ｂ２ ３９２（図３Ｂ）に対応する。すなわち、ポリゴンＳ２ ５４４２内の各点は、束Ｂ２ ３９２内の円弧の中心に対応する。図５Ｂにおいて、重複領域α５４４３は、ポリゴンＳ１ ５４４１とポリゴンＳ２ ５４４２の間の交差を表す。したがって重複領域α５４４３内のすべての点は物理的な点Ｐ１ ３０６、物理的な点Ｐ２ ３２６、物理的な点Ｐ３ ３４６、および物理的な点Ｐ４ ３６６を接続する円弧の中心に対応する。各円弧の、各対応する基準点Ｐ１ ３０２、Ｐ２ ３２２、Ｐ３ ３４２、およびＰ４ ３６２からの偏差は各基準点（それぞれ、Ｒ１ ３０４、Ｒ２ ３２４、Ｒ３ ３４４、Ｒ４ ３６４）に付随する許容偏差以下である。] 図３Ａ 図３Ｂ 図５Ｂ
[0028] 本工程は、（先に図７の流れ図に示した）直線セグメントのステップのシーケンスと同様のステップのシーケンスに従って、追加の隣接する物理的な点に対して繰り返すことが可能である。シーケンシャルな円弧の束に対応するシーケンシャルなポリゴンが、既存の交差領域と次のポリゴンとの交差がヌルになるまで、図５Ｂに加えられる。
αｆ∩Ｓｆ＋１＝φ] 図５Ｂ 図７
[0029] 次に、最終交差領域αｆの幾何学的基準中心点が決定される。αｆの幾何学的基準中心点をパラメトリックな点Ｖｆ（ｘｆ／ｙｆ）として指定する。これが最初のＴ＝ｆ＋２個の隣接する物理的な点間の最良適合近似の円弧の中心点であり、それによって円弧の各対応する基準点からの偏差が、各基準点に付随する許容偏差以下であるようにする。したがって最小および最大の半径は、各近似点に対し、その許容偏差を使用して定義される。通過点の半径の領域の交差全体がヌルでない場合は、最良適合の円弧が存在し、その半径は半径の範囲の中央値であるとして選択される。［注意：この例では円弧が３点を接続するのでＴ＝ｆ＋２であるが、直線セグメントは２点を接続する。］]
[0030] 図６は、物理的な点の複雑な順序集合を示す。各物理的な点は、その中心点が対応する基準点であり、半径がそれに付随する許容偏差である、円で表される。上述の方法を実行するコンピュータプログラムは、直線セグメントおよび円弧を接続した配列を含む近似曲線で、物理的な点を接続した。] 図６
[0031] 上述の例は２次元空間に適合するものである。本発明の実施形態は３次元空間に適合され得る。物理的空間内の物理的な点の集合順序集合が入力として与えられる。先に検討したように各物理的な点は、対応する基準点に位置する中心点および付随する許容偏差に対応する半径を有する、球で表され得る。幾何学的要素が、物理的な点の集合から選択された隣接する物理的な点のサブグループを近似するために選択される。幾何学的要素の例には直線セグメントおよび円弧を含むが、適用分野に応じて、より複雑な幾何学的要素も選択され得る。隣接する物理的な点のサブグループを接続するために、幾何学的要素の束が生成される。（束内の）各幾何学的要素の対応する各基準点からの偏差は、各基準点に付随する許容偏差以下である（各基準点に付随する許容偏差より大きくない）。]
[0032] 各幾何学的要素は、パラメトリック空間内のパラメトリックな点に写像され、各幾何学的要素の束はパラメトリック空間内の領域に写像される。パラメトリック空間が物理的空間であることもある。本発明の一実施形態において、３次元領域はポリへドロンで近似され、ポリへドロン内のすべての点はパラメトリック空間内のパラメトリックな点のマニホルドのメンバである。２次元の場合と同様に、束のシーケンスが生成される。各束は物理的な点のシーケンシャルなサブグループを接続する。各束は、パラメトリック空間内のポリへドロンに写像される。第１の束は第１のポリへドロンに写像される。第２の束は第２のポリへドロンに写像される。第１のポリへドロンと第２のポリへドロンが交差すると、その交差領域は第１の交差ポリへドロンと呼ばれる。第１の交差ポリへドロン内の点は写像により幾何学的要素の集合になり、それは最初の２つの物理的な点が結合されたサブグループ内の物理的な点のシーケンスを近似するものである。第１の交差ポリへドロンの中心は写像により、結合された最初の２つのサブグループ内の物理的な点を接続する、幾何学的要素の最良適合近似になる。]
[0033] 本工程は繰り返し可能である。第３の束は第３のポリへドロンに写像される。第３のポリへドロンが第１の交差ポリへドロンと交差する場合、新しい交差領域は第２の交差ポリへドロンと呼ばれる。第２の交差ポリへドロン内の点は写像により、結合された最初の３つの物理的な点のサブグループ内の物理的な点の集合を近似する、幾何学的要素の集合になる。第２の交差ポリへドロンの中心は写像により、最初の３つのサブグループ内の物理的な点を接続する、幾何学的要素の最良適合近似になる。この繰り返しは次の条件のうちの１つが成立するまで続けられる。（ａ）現在の非ヌル交差ポリへドロンと（写像により次の束になる）次のポリへドロンとの交差がヌルである場合、または（ｂ）すべての物理的な点が処理された場合。最終の非ヌル交差ポリへドロンの中心は写像により、最終非ヌル交差ポリへドロンに写像された結合されたサブグループ内の物理的な点を接続する、幾何学的要素の最良適合近似になる。結合されたサブグループ内の各対応する基準点からの、幾何学的要素の最良適合近似の偏差は、各基準点に付随する許容偏差以下である（各基準点に付随する許容偏差よりも大きくない）。]
[0034] 本明細書で「ポリトープ」という用語は、２次元空間内でポリゴンを、３次元空間内でポリへドロンをいう。]
[0035] 異なる幾何学的要素が逐次的に使用され得ることに注意されたい。例えば曲線経路は、ほぼ直線部分に沿った直線セグメントと、曲線部分に沿った円弧で近似され得る。]
[0036] 本発明の実施形態はコンピュータで実施され得る。図８に示すように、コンピュータ８０２は、中央処理装置ＣＰＵ８０４、メモリ８０８、データ記憶装置８０６、およびユーザ入／出力インターフェイス８１０を含む、任意の型式のよく知られたコンピュータであってよい。データ記憶装置８０６は、ハード・ドライブ、不揮発性メモリ、またはその他の（磁気ディスク、またはコンパクトディスク読み出し専用メモリのような）コンピュータ可読媒体を含んでよい。ユーザ入／出力インターフェイス８１０は、キーボードまたはマウスなどのユーザ入／出力装置８２０への接続部を含んでよく、それによってユーザはコンピュータ８０２との相互作用が可能になる。] 図８
[0037] よく知られているように、コンピュータは、コンピュータの全体的なオペレーションとアプリケーションを規定するコンピュータソフトウェアの制御下で動作する。ＣＰＵ８０４は、全体的なオペレーションおよびアプリケーションを規定するコンピュータプログラムの命令を実行することにより、コンピュータの全体的なオペレーションおよびアプリケーションを制御する。コンピュータプログラム命令は、データ記憶装置８０６内に記憶され、プログラムの命令実行が望まれるときにメモリ８０８内にロードされる。図７の方法ステップは、コンピュータプログラム命令によって規定され、メモリ８０８内またはデータ記憶装置８０６内（またはメモリ８０８とデータ記憶装置８０６の組合せ内）に記憶され、コンピュータプログラム命令を実行するＣＰＵ８０４によって制御される。例えば、図７の方法ステップを実施するアルゴリズムを遂行するために、コンピュータプログラム命令は、当業者によってプログラムされたコンピュータで実行可能なコードとして実施され得る。したがってＣＰＵ８０４は、コンピュータプログラム命令を実行することにより、図７の方法ステップを実施するアルゴリズムを実行する。] 図７
[0038] コンピュータ８０２はさらに、ＣＰＵ８０４からの信号を、ビデオディスプレイ８２６を駆動し得る信号に変換するビデオディスプレイ・インターフェイス８１６を含んでよい。コンピュータ８０２はさらに、１つまたは複数のネットワーク・インターフェイスを含んでよい。例えば、通信ネットワーク・インターフェイス８１８は、インターネットプロトコル（ＩＰ）通信ネットワーク８２８への接続部を含んでよく、それはユーザ、制御、およびテストトラフィックを輸送可能である。通信ネットワーク・インターフェイス８１８は、有線、無線、および光ファイバを含む様々な物理的インターフェイスを含み得る。コンピュータ８０２はさらに、外部データ記憶インターフェイス８１４を含み得る。アルゴリズムによって解析された結果は、外部データ記憶インターフェイス８１４を通して輸送され、外部データ記憶ユニット８２４内に記憶され得る。当業者は、現実のコンピュータでの実行には、さらに他の構成要素も含み得ること、および図８は例示目的のために、コンピュータのいくつかの構成要素を高いレベルで表現したものであることを認識するであろう。] 図８
[0039] 図９Ａおよび９Ｂは、本発明の一実施形態による車両を自動誘導する方法を例示するものである。図９Ａにおいて、全地球測位システム（ＧＰＳ）受信機９８０はユーザ指定された経路（道路のような）に沿って増分しながら移動して、物理的な点Ｐ１ ９０２〜Ｐ２２ ９４４を含む物理的な点の座標（９０１）の順序集合を記録する。図９Ｂにおいて、物理的な点９０１の順序集合がコンピュータ８０２にアップロードされる。一実施形態において、データはＧＰＳ受信機９８０から無線インターフェイスを経てコンピュータ８０２に送信され得る。別の実施形態において、データはＧＰＳ受信機９８０に保存され、ローカルユーザ入／出力インターフェイス８１０、または遠隔通信ネットワーク・インターフェイス８１８（図８）を通して、コンピュータ８０２に転送され得る。コンピュータ８０２は、本発明の一実施形態に従って、アルゴリズムのステップを遂行するためにコンピュータ命令を実行する。コンピュータ８０２は入力された物理的な点９０１の順序集合を、物理的な点９０１の順序集合を近似する幾何学的要素９０３の出力シーケンスに変換する。この例では、幾何学的要素のシーケンス９０３は直線セグメントＬ１ ９０５、直線セグメントＬ２ ９０７、円弧Ａ１ ９０９、直線セグメントＬ３ ９１１、円弧 Ａ２ ９１３、および直線セグメントＬ４ ９１５を含む。] 図８ 図９Ａ 図９Ｂ
[0040] 次に幾何学的要素９０３のシーケンスが、車両９８４に搭載されている誘導制御システム９８２にダウンロードされる。一実施形態において、データはコンピュータ８０２から無線インターフェイスを経て、誘導制御システム９８２に転送される。当業者は別のシステム構成を実現してよい。例えば、ＧＰＳ受信機９８０、コンピュータ８０２、および誘導制御システム９８２は、車両９８４に搭載された単一のシステムに統合されてよい。誘導経路９３１に沿って車両９８４を自動操縦する誘導制御システム９８２は、操縦システムを制御し、車両は物理的な点９０１の集合順序集合を通過する。自動誘導された車両は様々な応用に使用され得る。例えば、車両９８４は道路整地に使用されるドーザであってよい。別の例として、カメラシステムを車両９８４に搭載してよく、それは自動検査用に使用される。]
[0041] 上述した「発明を実施するための形態」は、それぞれの事項において例示的、代表的なものであって、限定するものではなく、本明細書に開示された本発明の範囲は、「発明を実施するための形態」から決められるものではなく、特許法によって許可された全幅に従って記述された特許請求の範囲によって決定されるものと理解されるべきである。本明細書に示され、説明された実施形態は、本発明の原理を単に例示したものであって、本発明の範囲と精神から逸脱することなく、当業者によって様々な修正が実施され得るものと理解されるべきである。当業者は、本発明の範囲と精神から逸脱することなく、様々な別の特徴の組合せを実施することができる。]

权利要求:

請求項1
各物理的な点が基準点と付随する許容偏差とを含む、物理的空間内の物理的な点の順序集合を近似するための方法において、前記物理的な点の順序集合から選択された物理的な点の第１のサブグループを接続する幾何学的要素の第１の束を生成するステップであって、前記第１の束内の各幾何学的要素の、前記第１のサブグループ内の各基準点からの偏差が、前記第１のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第１の束をパラメトリック空間内の第１のポリトープに写像するステップであって、前記第１の束内の各幾何学的要素が前記第１のポリトープ内の対応するパラメトリックな点に写像されるステップと、前記物理的な点の順序集合から選択された物理的な点の第２のサブグループを接続する幾何学的要素の第２の束を生成するステップであって、前記第２の束内の各幾何学的要素の、前記第２のサブグループ内の各基準点からの偏差が、前記第２のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第２の束を前記パラメトリック空間内の第２のポリトープに写像するステップであって、前記第２の束内の各幾何学的要素が前記第２のポリトープ内の対応するパラメトリックな点に写像されるステップとを含む方法。
請求項2
前記第１のポリトープと前記第２のポリトープとの間の第１の交差領域を決定するステップと、前記第１の交差領域がヌルの場合は、前記第１のポリトープの中心を決定するステップと、前記第１のポリトープの前記中心を対応する幾何学的要素に写像するステップとを、前記第１の交差領域がヌルでない場合は、前記物理的な点の順序集合から選択された物理的な点の第３のサブグループを接続する幾何学的要素の第３の束を生成するステップであって、前記第３の束内の各幾何学的要素の、前記第３のサブグループ内の各基準点からの偏差が、前記第３のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第３の束を前記パラメトリック空間内の第３のポリトープに写像するステップであって、前記第３の束内の各幾何学的要素が前記第３のポリトープ内の対応するパラメトリックな点に写像されるステップとをさらに含む、請求項１に記載の方法。
請求項3
前記第１の交差領域と前記第３のポリトープとの間の第２の交差領域を決定するステップと、前記第２の交差領域がヌルの場合は、前記第１の交差領域の中心を決定するステップと、前記第１の交差領域の前記中心を対応する幾何学的要素に写像するステップとを、前記第２の交差領域がヌルでない場合は、前記物理的な点の順序集合から選択された物理的な点の第４のサブグループを接続する幾何学的要素の第４の束を生成するステップであって、前記第４の束内の各幾何学的要素の、前記第４のサブグループ内の各基準点からの偏差が、前記第４のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第４の束を前記パラメトリック空間内の第４のポリトープに写像するステップであって、前記第４の束内の各幾何学的要素が前記第４のポリトープ内の対応するパラメトリックな点に写像されるステップとをさらに含む、請求項２に記載の方法。
請求項4
前記ポリトープがポリへドロンである、請求項１に記載の方法。
請求項5
前記ポリトープがポリゴンである、請求項１に記載の方法。
請求項6
幾何学的要素の第１の束を生成する前記ステップが、直線セグメントの第１の束を生成するステップであって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合であるステップを含み、前記第１の束を第１のポリトープに写像する前記ステップが前記第１の束内の各特定の直線セグメントを、前記パラメトリック空間内の座標（Ｃ１／Ｂ１，Ａ１／Ｂ１）の特定の集合で定義された特定のパラメトリックな点に写像するステップを含み、幾何学的要素の第２の束を生成する前記ステップが、直線セグメントの第２の束を生成するステップであって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合であるステップを含み、前記第２の束を第２のポリトープに写像する前記ステップが、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ｂ２，Ａ２／Ｂ２）の特定の集合で定義された特定のパラメトリックな点に写像するステップを含む、請求項１に記載の方法。
請求項7
幾何学的要素の第１の束を生成する前記ステップが、直線セグメントの第１の束を生成するステップであって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合であるステップを含み、前記第１のポリトープに前記第１の束を写像するステップが前記第１の束内の各特定の直線セグメントを、パラメトリック空間内の座標（Ｃ１／Ａ１，Ｂ１／Ａ１）の特定の集合で定義された特定のパラメトリックな点に写像するステップを含み、幾何学的要素の第２の束を生成する前記ステップが、直線セグメントの第２の束を生成するステップであって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合であるステップを含み、前記第２の束を第２のポリトープに写像する前記ステップが、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ａ２，Ｂ２／Ａ２）の特定の集合で定義された特定のパラメトリックな点に写像するステップを含む、請求項１に記載の方法。
請求項8
幾何学的要素の第１の束を生成する前記ステップが、円弧の第１の束を生成するステップであって、前記第１の束内の各円弧が対応する中心点および対応する半径を有するステップを含み、前記第１の束を第１のポリトープに写像する前記ステップが、前記円弧の第１の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するステップを含み、幾何学的要素の第２の束を生成する前記ステップが、円弧の第２の束を生成するステップであって、前記第２の束内の各円弧が対応する中心点および対応する半径を有するステップを含み、前記第２の束を第２のポリトープに写像する前記ステップが、前記円弧の第２の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するステップを含む、請求項１に記載の方法。
請求項9
各物理的な点が基準点と付随する許容偏差とを含む、物理的空間内の物理的な点の順序集合を近似するための装置において、前記物理的な点の順序集合から選択された物理的な点の第１のサブグループを接続する幾何学的要素の第１の束を生成するための手段であって、前記第１の束内の各幾何学的要素の、前記第１のサブグループ内の各基準点からの偏差が、前記第１のサブグループ内の各基準点に付随する許容偏差を超えない手段と、前記第１の束をパラメトリック空間内の第１のポリトープに写像するための手段であって、前記第１の束内の各幾何学的要素が前記第１のポリトープ内の対応するパラメトリックな点に写像される手段と、前記物理的な点の順序集合から選択された物理的な点の第２のサブグループを接続する幾何学的要素の第２の束を生成するための手段であって、前記第２の束内の各幾何学的要素の、前記第２のサブグループ内の各基準点からの偏差が、前記第２のサブグループ内の各基準点に付随する許容偏差を超えない手段と、前記第２の束を前記パラメトリック空間内の第２のポリトープに写像するための手段であって、前記第２の束内の各幾何学的要素が前記第２のポリトープ内の対応するパラメトリックな点に写像される手段とを含む装置。
請求項10
前記第１のポリトープと前記第２のポリトープとの間の第１の交差領域を決定するための手段と、前記第１のポリトープの中心を決定するための手段と、前記第１のポリトープの前記中心を対応する幾何学的要素に写像するための手段と、前記物理的な点の順序集合から選択された物理的な点の第３のサブグループを接続する幾何学的要素の第３の束を生成するための手段であって、前記第３の束内の各幾何学的要素の、前記第３のサブグループ内の各基準点からの偏差が、前記第３のサブグループ内の各基準点に付随する許容偏差を超えない手段と、前記第３の束を前記パラメトリック空間内の第３のポリトープに写像するための手段であって、前記第３の束内の各幾何学的要素が前記第３のポリトープ内の対応するパラメトリックな点に写像される手段とをさらに含む、請求項９に記載の装置。
請求項11
前記第１の交差領域と前記第３のポリトープとの間の第２の交差領域を決定するための手段と、前記第１の交差領域の中心を決定するための手段と、前記第１の交差領域の前記中心を対応する幾何学的要素に写像するための手段と、前記物理的な点の順序集合から選択された物理的な点の第４のサブグループを接続する幾何学的要素の第４の束を生成するための手段であって、前記第４の束内の各幾何学的要素の、前記第４のサブグループ内の各基準点からの偏差が、前記第４のサブグループ内の各基準点に付随する許容偏差を超えない手段と、前記第４の束を前記パラメトリック空間内の第４のポリトープに写像するための手段であって、前記第４の束内の各幾何学的要素が前記第４のポリトープ内の対応するパラメトリックな点に写像される手段とをさらに含む、請求項１０に記載の装置。
請求項12
直線セグメントの第１の束を生成するための手段であって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合である手段と、前記第１の束内の各特定の直線セグメントを、前記パラメトリック空間内の座標（Ｃ１／Ｂ１，Ａ１／Ｂ１）の特定の集合で定義された特定のパラメトリックな点に写像する手段と、直線セグメントの第２の束を生成する手段であって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合である手段と、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ｂ２，Ａ２／Ｂ２）の特定の集合で定義された特定のパラメトリックな点に写像する手段とをさらに含む、請求項９に記載の装置。
請求項13
直線セグメントの第１の束を生成するための手段であって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合である手段と、前記第１の束内の各特定の直線セグメントを、前記パラメトリック空間内の座標（Ｃ１／Ａ１，Ｂ１／Ａ１）の特定の集合で定義された、特定のパラメトリックな点に写像する手段と、直線セグメントの第２の束を生成する手段であって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合である手段と、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ａ２，Ｂ２／Ａ２）の特定の集合で定義された特定のパラメトリックな点に写像する手段とをさらに含む、請求項９に記載の装置。
請求項14
円弧の第１の束を生成するための手段であって、前記第１の束内の各円弧が対応する中心点および対応する半径を有する手段と、前記円弧の第１の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するための手段と、円弧の第２の束を生成するための手段であって、前記第２の束内の各円弧が対応する中心点および対応する半径を有する手段と、前記円弧の第２の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するための手段とをさらに含む、請求項９に記載の装置。
請求項15
各物理的な点が基準点と付随する許容偏差とを含む、物理的空間内の物理的な点の順序集合を近似するためのコンピュータ命令を記憶するコンピュータ可読媒体において、前記コンピュータ命令が、前記物理的な点の順序集合から選択された物理的な点の第１のサブグループを接続する幾何学的要素の第１の束を生成するステップであって、前記第１の束内の各幾何学的要素の、前記第１のサブグループ内の各基準点からの偏差が、前記第１のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第１の束をパラメトリック空間内の第１のポリトープに写像するステップであって、前記第１の束内の各幾何学的要素が前記第１のポリトープ内の対応するパラメトリックな点に写像されるステップと、前記物理的な点の順序集合から選択された物理的な点の第２のサブグループを接続する幾何学的要素の第２の束を生成するステップであって、前記第２の束内の各幾何学的要素の、前記第２のサブグループ内の各基準点からの偏差が、前記第２のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第２の束を前記パラメトリック空間内の第２のポリトープに写像するステップであって、前記第２の束内の各幾何学的要素が前記第２のポリトープ内の対応するパラメトリックな点に写像されるステップとを規定する、コンピュータ可読媒体。
請求項16
前記コンピュータプログラム命令が、前記第１のポリトープと前記第２のポリトープとの間の第１の交差領域を決定するステップと、前記第１の交差領域がヌルの場合は、前記第１のポリトープの中心を決定するステップと、前記第１のポリトープの前記中心を対応する幾何学的要素に写像するステップとを、前記第１の交差領域がヌルでない場合は、前記物理的な点の順序集合から選択された物理的な点の第３のサブグループを接続する幾何学的要素の第３の束を生成するステップであって、前記第３の束内の各幾何学的要素の、前記第３のサブグループ内の各基準点からの偏差が、前記第３のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第３の束を前記パラメトリック空間内の第３のポリトープに写像するステップであって、前記第３の束内の各幾何学的要素が前記第３のポリトープ内の対応するパラメトリックな点に写像されるステップとを規定するコンピュータプログラム命令をさらに含む、請求項１５に記載のコンピュータ可読媒体。
請求項17
前記コンピュータプログラム命令が、前記第１の交差領域と前記第３のポリトープとの間の第２の交差領域を決定するステップと、前記第２の交差領域がヌルの場合は、前記第１の交差領域の中心を決定するステップと、前記第１の交差領域の前記中心を対応する幾何学的要素に写像するステップとを、前記第２の交差領域がヌルでない場合は、前記物理的な点の順序集合から選択された物理的な点の第４のサブグループを接続する幾何学的要素の第４の束を生成するステップであって、前記第４の束内の各幾何学的要素の、前記第４のサブグループ内の各基準点からの偏差が、前記第４のサブグループ内の各基準点に付随する許容偏差を超えないステップと、前記第４の束を前記パラメトリック空間内の第４のポリトープに写像するステップであって、前記第４の束内の各幾何学的要素が前記第４のポリトープ内の対応するパラメトリックな点に写像されるステップとを規定するコンピュータプログラム命令をさらに含む、請求項１６に記載のコンピュータ可読媒体。
請求項18
前記コンピュータプログラム命令が、直線セグメントの第１の束を生成するステップであって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合であるステップと、前記第１の束内の各特定の直線セグメントを、前記パラメトリック空間内の座標（Ｃ１／Ｂ１，Ａ１／Ｂ１）の特定の集合で定義された特定のパラメトリックな点に写像するステップと、直線セグメントの第２の束を生成するステップであって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合であるステップと、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ｂ２，Ａ２／Ｂ２）の特定の集合で定義された特定のパラメトリックな点に写像するステップとを規定するコンピュータプログラム命令をさらに含む、請求項１５に記載のコンピュータ可読媒体。
請求項19
前記コンピュータプログラム命令が、直線セグメントの第１の束を生成するステップであって、各特定の直線セグメントが式Ａ１＊ｘ＋Ｂ１＊ｙ＋Ｃ１＝０で定義される特定の線に対応するセグメントであり、ここでｘおよびｙは２次元物理的空間内の直交軸であり、（Ａ１，Ｂ１，Ｃ１）は前記第１の束内の対応する線形係数の特定の集合であるステップと、前記第１の束内の各特定の直線セグメントを、前記パラメトリック空間内の座標（Ｃ１／Ａ１，Ｂ１／Ａ１）の特定の集合で定義された特定のパラメトリックな点に写像するステップと、直線セグメントの第２の束を生成するステップであって、各特定の直線セグメントが式Ａ２＊ｘ＋Ｂ２＊ｙ＋Ｃ２＝０で定義される特定の線に対応するセグメントであり、ここで（Ａ２，Ｂ２，Ｃ２）は前記第２の束内の線形係数の特定の集合であるステップと、前記第２の束内の各特定の直線セグメントを、座標（Ｃ２／Ａ２，Ｂ２／Ａ２）の特定の集合で定義された特定のパラメトリックな点に写像するステップとを規定するコンピュータプログラム命令をさらに含む、請求項１５に記載のコンピュータ可読媒体。
請求項20
前記コンピュータプログラム命令が、円弧の第１の束を生成するステップであって、前記第１の束内の各円弧が対応する中心点および対応する半径を有するステップと、前記円弧の第１の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するステップと、円弧の第２の束を生成するステップであって、前記第２の束内の各円弧が対応する中心点および対応する半径を有するステップと、前記円弧の第２の束内の各特定の円弧を、前記特定の円弧に対応する特定の中心点に写像するステップとを規定するコンピュータプログラム命令をさらに含む、請求項１５に記載のコンピュータ可読媒体。